package 剑指offer;

public class _49丑数 {
	/**
	 * 
	 *@time 2021年3月20日上午10:40:58
	 * 
	 *@param n
	 *@return int
	 *
	 *@see
	 *设已知长度为 nn 的丑数序列 x_1, x_2,.... , x_n,求第 n+1 个丑数 x_{n+1} 
	 *根根据递推性质，丑数 x_{n+1}  只可能是以下三种情况其中之一:
	 *
	 *1.x_n+1=x_a*2
	 *2.x_n+1=x_b*3
	 *3.x_n+1=x_c*5
	 *丑数递推公式： 若索引 a,b,c 满足以上条件，则下个丑数 x_{n+1}为以下三种情况中的 最小值 ；
	 *					x_n+1=min{x_a*2,x_b*3,x_c*5}
	 *
	 */
    public int nthUglyNumber(int n) {
    	int a=1,b=1,c=1;
    	int []dp = new int[n+1];   	
    	dp[1] = 1;
    	for (int i = 2; i <= n; i++) {
			int n1 = dp[a]*2,n2 = dp[b]*3,n3 = dp[c]*5;
			dp[i] = Math.min(Math.min(n1,n2), n3);
			//这里都用if语句是因为当两个以上的数都是最小时，让他们都加上1
			if (dp[i] == n1) a++;
			if (dp[i] == n2) b++; 
			if (dp[i] == n3) c++;		
		}
    		
		return dp[n];
    }

}
